/*	Stack ADT Type Defintions 
	   Written by: F & G
	   Date:       2/98
	
	   Revised:    4/99--converted to C++  
	
	Brooks/Cole 
	A division of Thomson Learning
	Copyright 2001 All Rights Reserved 
*/
//	Node Declaration

	template<class TYPE>
	struct Node 
	   {
	    TYPE  data;
	    Node<TYPE> *next;
	   };

//	Class Declaration
	template<class TYPE>
	class Stack
	{
	 private: 
	    int         count; 
	    Node<TYPE> *top; 
	
	 public:
	         Stack      (void);
	        ~Stack      (void);
	   bool  pushStack  (TYPE  dataIn);
	   bool  popStack   (TYPE& dataOut);
	   bool  stackTop   (TYPE& dataOut);
	   bool  emptyStack (void);
	   bool  fullStack  (void);
	   int   stackCount (void);  
	};  // class Stack

/*	=============== Constructor ==============	
	This algorithm creates an empty stack.
	   Pre  Nothing
	   Post Stack created and initialized
*/

template<class TYPE>
Stack<TYPE> :: Stack (void)
{
//	Statements  
	top   = NULL;
	count = 0;
}	// Constructor 

/*	=================== pushStack =================== 
	This function pushes an item onto the stack.
	   Pre     dataIn contains data to be inserted
	   Returns true if success; false if overflow
*/

template<class TYPE> 
bool Stack<TYPE> ::  pushStack (TYPE dataIn)
{
//	Local Definitions 
	bool         success;
	Node<TYPE>  *newPtr;

//	Statements 
	if (!(newPtr =  new Node<TYPE>))
	    success  = false;
	else
	   {
	    newPtr->data = dataIn; 
	    newPtr->next = top; 
	    top          = newPtr; 
	    count ++;
	    success      = true;
	   } // else 
	return success;
}	// pushStack 

/*	=============== popStack ============== 
	This function pops the item on the top of the stack.
	   Pre     dataOut is variable to receive data
	   Post    popped data in dataOut 
	   Returns true if successful, false if underflow
*/

template<class TYPE>
bool Stack<TYPE> :: popStack (TYPE& dataOut) 
{
//	Local Definitions
	Node<TYPE>  *dltPtr;
	bool         success;
	
//	Statements 
	if (count == 0)
        success = false;
	else
	   {
	    dltPtr  = top;
	    dataOut = top->data;
	    top     = top->next;
	    count--;
	    delete dltPtr;
	    success = true;
	   } //  else 
	return success;
}	// popStack 

/*	==================== stackTop =================== 
	This function retrieves the data from the top of the 
	stack without changing the stack.
	   Pre     dataOut is variable to receive data
	   Post    data in dataOut 
	   Returns true if successful, false if underflow
*/

template<class TYPE> 
bool Stack<TYPE> :: stackTop (TYPE& dataOut) 
{
//	Local Definitions 
	bool success;
	
//	Statements 
	if (count == 0)
	   success = false;
	else
	   {
	    dataOut = top->data;
	    success = true;
	   } // else
	return success;
}	// stackTop 

/*	================= emptyStack ================ 
	This function determines if a stack is empty. 
	   Pre     nothing
	   Returns true if empty, false if data in stack 
*/

template<class TYPE>
bool Stack<TYPE> :: emptyStack (void) 
{
//	Statements 
	return (count == 0);
}	// emptyStack 

/*	=================== fullStack =================== 
	This function determines if a stack is full.
	Full is defined as heap full.
	    Pre     nothing
	    Returns true if heap full, false if room 
*/

template<class TYPE> 
bool Stack <TYPE> :: fullStack (void) 
{
//	Local Definitions  
	Node<TYPE>  *temp;

//	Statements 
	temp = new Node<TYPE>;
   if (temp != NULL)
	   {
	    delete  temp;
	    return false;
	   } // if

	// allocation failed 
	return true;
}	// fullStack 

/*	==================== stackCount =================== 
	Returns the number of elements in the stack.
	   Pre   nothing
	   Post  count returned
*/

template<class TYPE> 
int Stack <TYPE> :: stackCount(void) 
{
//	Statements 
	return count;
}	//  stackCount 

/*	=============== Destructor  ============== 
	This function releases all nodes to the heap.
	   Pre   stack being destroyed
	   Post  stack and data deleted
*/

template<class TYPE>
Stack<TYPE> :: ~Stack (void) 
{
//	Local Definitions 
	Node<TYPE>  *temp;

//	Statements 
	//  Delete all nodes in stack 
	while (top != NULL) 
	   {
	    temp = top;
	    top  = top->next; 
	    delete temp; 
	   } //  while 
}	// Destructor 
